package org.example.Soution001;

public class MaxPath {
    public static void main(String[] args){
        MaxPath max=new MaxPath();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(-2);
        root.right = new TreeNode(3);
//        root.right.left = new TreeNode(15);
//        root.right.right = new TreeNode(7);
//        root.right.right = new TreeNode(56);
        System.out.println(max.maxPathSum(root));
    }

    int maxSum=0;
    public int maxPathSum(TreeNode root) {
        maxSum=root.val;
        getNodeMaxSumAndMaxCount(root);
        //如果root比较大其数值也被maxSum得到了
        return maxSum;
    }

    public int getNodeMaxSumAndMaxCount(TreeNode root) {
        if(root==null) return 0;
        int leftmax=getNodeMaxSumAndMaxCount(root.left);
        int rightmax=getNodeMaxSumAndMaxCount(root.right);
        int nodeMaxVal=root.val+(leftmax>0?leftmax:0)+(rightmax>0?rightmax:0);
        maxSum=Math.max(maxSum,nodeMaxVal);
        return Math.max(root.val,Math.max(leftmax,rightmax)+root.val);
    }
}
